A storage system typically comprises one or more storage devices into which information may be entered, and from which information may be obtained, as desired. The storage system includes a storage operating system that functionally organizes the system by, inter alia, invoking storage operations in support of a storage service implemented by the system. The storage system may be implemented in accordance with a variety of storage architectures including, but not limited to, a network-attached storage (NAS) environment, a storage area network (SAN) and a disk assembly directly attached to a client or host computer. The storage devices are typically disk drives organized as a disk array, wherein the term “disk” commonly describes a self-contained rotating magnetic media storage device. The term disk in this context is synonymous with hard disk drive (HDD) or direct access storage device (DASD).
Storage of information on the disk array is preferably implemented as one or more storage “volumes” of physical disks, defining an overall logical arrangement of disk space. The disks within a volume are typically organized as one or more groups, wherein each group may be operated as a Redundant Array of Independent (or Inexpensive) Disks (RAID). Most RAID implementations enhance the reliability/integrity of data storage through the redundant writing of data “stripes” across a given number of physical disks in the RAID group, and the appropriate storing of redundant information (parity) with respect to the striped data. The physical disks of each RAID group may include disks configured to store striped data (i.e., data disks) and disks configured to store parity for the data (i.e., parity disks). The parity may thereafter be retrieved to enable recovery of data lost when a disk fails. The term “RAID” and its various implementations are well-known and disclosed in A Case for Redundant Arrays of Inexpensive Disks (RAID), by D. A. Patterson, G. A. Gibson and R. H. Katz, Proceedings of the International Conference on Management of Data (SIGMOD), June 1988.
The storage operating system of the storage system may implement a high-level module, such as a file system, to logically organize the information stored on the disks as a hierarchical structure of data containers, such as directories, files and blocks. For example, each “on-disk” file may be implemented as set of data structures, i.e., disk blocks, configured to store information, such as the actual data for the file. These data blocks are organized within a volume block number (vbn) space that is maintained by the file system. The file system organizes the data blocks within the vbn space as a “logical volume”; each logical volume may be, although is not necessarily, associated with its own file system. The file system typically consists of a contiguous range of vbns from zero to n, for a file system of size n+1 blocks.
A known type of file system is a write-anywhere file system that does not overwrite data on disks. If a data block is retrieved (read) from disk into a memory of the storage system and “dirtied” (i.e., updated or modified) with new data, the data block is thereafter stored (written) to a new location on disk to optimize write performance. A write-anywhere file system may initially assume an optimal layout such that the data is substantially contiguously arranged on disks. The optimal disk layout results in efficient access operations, particularly for sequential read operations, directed to the disks. An example of a write-anywhere file system that is configured to operate on a storage system is the Write Anywhere File Layout (WAFL®) file system available from Network Appliance, Inc., of Sunnyvale, Calif.
The storage system may be configured to operate according to a client/server model of information delivery to thereby allow many clients to access the directories, files and blocks stored on the system. In this model, the client may comprise an application, such as a database application, executing on a computer that “connects” to the storage system over a computer network, such as a point-to-point link, shared local area network, wide area network or virtual private network implemented over a public network, such as the Internet. Each client may request the services of the file system by issuing file system protocol messages (in the form of packets) to the storage system over the network. By supporting a plurality of file system protocols, such as the conventional Common Internet File System (CIFS) and the Network File System (NFS) protocols, the utility of the storage system is enhanced.
Some file systems, including the exemplary WAFL file system described above may implement virtual disks (vdisks), which are encapsulated data containers stored within a file system. An example of such a storage appliance is described in U.S. patent application Ser. No. 10/215,917, entitled MULTI-PROTOCOL STORAGE APPLIANCE THAT PROVIDES INTEGRATED SUPPORT FOR FILE AND BLOCK ACCESS PROTOCOLS, by Brian Pawlowski, et al., the contents of which are hereby incorporated by reference. Similarly, vdisks are described in U.S. patent application Ser. No. 10/216,453, entitled STORAGE VIRTUALIZATION BY LAYERING VIRTUAL DISK OBJECTS ON A FILE SYSTEM, by Vijayan Rajan, et al., the contents of which are hereby incorporated by reference.
Storage system administrators often desire to rapidly obtain information, i.e., metadata, relating to the data containers stored within storage systems. As used herein, metadata denotes the attributes associated with a data container other than the actual data contents of the data container. In addition, data containers may denote a file, a directory, a virtual disk (vdisk), or other data construct that is addressable via a storage system. Examples of metadata relating to a data container that may be of interest include, e.g., file name, file type, file size, modification time, etc. Administrators typically desire fast access to metadata to be able to answer such questions as the identity of the largest files within the storage system, the percentage of files within a storage system that are of a particular type, etc. By quickly determining such information, administrators may more effectively manage storage and permit users to better manage their own storage.
To identify the metadata information desired, an administrator may need to examine all of the data containers within a storage system every time such information is requested. In modern storage systems, which may have the tens or hundreds of millions of data containers, this is clearly not a practical solution. Another solution is to generate a database of metadata associated with the file system to enable faster searching. The metadata database may be constructed by performing a file system “crawl” through the entire file system. As used herein, a file system crawl involves accessing every data container within the file system to obtain the necessary metadata. However, such a file system crawl is expensive both in terms of disk input/output operations and processing time and suffers from the same practical problems of directly accessing each data container. That is, the file system crawl may slow access to the file system for tens of minutes at a time, which results in an unacceptable loss of performance. Additionally, the file system crawl must be performed at regular intervals to maintain an up-to-date metadata database. As a result of the substantial processing time required, a further disadvantage of the file system crawl is that the metadata stored within the database may be inconsistent with the current state of the file system, i.e., the database only represents the metadata as of the completion of the last file system crawl.